Search Results

Documents authored by Keidar, Idit

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.15
Nova: Safe Off-Heap Memory Allocation and Reclamation

Authors: Ramy Fakhoury, Anastasia Braginsky, Idit Keidar, and Yoav Zuriel

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
In recent years, we begin to see Java-based systems embrace off-heap allocation for their big data demands. As of today, these system rely on simple ad-hoc garbage-collection solutions, which restrict the usage of off-heap data. This paper introduces the abstraction of safe off-heap memory allocation and reclamation (SOMAR), a thread-safe memory allocation and reclamation scheme for off-heap data in otherwise managed environments. SOMAR allows multi-threaded Java programs to use off-heap memory seamlessly. To realize this abstraction, we present Nova, Novel Off-heap Versioned Allocator, a lock-free SOMAR implementation. Our experiments show that Nova can be used to store off-heap data in Java data structures with better performance than ones managed by Java’s automatic GC. We further integrate Nova into the open-source Oak concurrent map library, which allows Oak to reclaim keys while the data structure is being accessed.
Cite as

Ramy Fakhoury, Anastasia Braginsky, Idit Keidar, and Yoav Zuriel. Nova: Safe Off-Heap Memory Allocation and Reclamation. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fakhoury_et_al:LIPIcs.OPODIS.2023.15,
  author =	{Fakhoury, Ramy and Braginsky, Anastasia and Keidar, Idit and Zuriel, Yoav},
  title =	{{Nova: Safe Off-Heap Memory Allocation and Reclamation}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{15:1--15:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.15},
  URN =		{urn:nbn:de:0030-drops-195052},
  doi =		{10.4230/LIPIcs.OPODIS.2023.15},
  annote =	{Keywords: memory reclamation, concurrency, performance, off-heap allocation}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.26
Cordial Miners: Fast and Efficient Consensus for Every Eventuality

Authors: Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Cordial Miners are a family of efficient Byzantine Atomic Broadcast protocols, with instances for asynchrony and eventual synchrony. They improve the latency of state-of-the-art DAG-based protocols by almost 2× and achieve optimal good-case complexity of O(n) by forgoing Reliable Broadcast as a building block. Rather, Cordial Miners use the blocklace - a partially-ordered counterpart of the totally-ordered blockchain data structure - to implement the three algorithmic components of consensus: Dissemination, equivocation-exclusion, and ordering.
Cite as

Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. Cordial Miners: Fast and Efficient Consensus for Every Eventuality. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{keidar_et_al:LIPIcs.DISC.2023.26,
  author =	{Keidar, Idit and Naor, Oded and Poupko, Ouri and Shapiro, Ehud},
  title =	{{Cordial Miners: Fast and Efficient Consensus for Every Eventuality}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.26},
  URN =		{urn:nbn:de:0030-drops-191525},
  doi =		{10.4230/LIPIcs.DISC.2023.26},
  annote =	{Keywords: Byzantine Fault Tolerance, State Machine Replication, DAG, Consensus, Blockchain, Blocklace, Cordial Dissemination}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.39
Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP

Authors: Shir Cohen and Idit Keidar

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
There have been several reductions from multivalued consensus to binary consensus over the past 20 years. To the best of our knowledge, none of them solved it for Byzantine asynchronous settings. In this short paper, we close this gap. Moreover, we do so in subquadratic communication, using newly developed subquadratic binary Byzantine Agreement techniques.
Cite as

Shir Cohen and Idit Keidar. Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 39:1-39:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.DISC.2023.39,
  author =	{Cohen, Shir and Keidar, Idit},
  title =	{{Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{39:1--39:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.39},
  URN =		{urn:nbn:de:0030-drops-191658},
  doi =		{10.4230/LIPIcs.DISC.2023.39},
  annote =	{Keywords: Byzantine agreement, subquadratic communication, fault tolerance in distributed systems}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.18
Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words

Authors: Shir Cohen, Idit Keidar, and Alexander Spiegelman

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Byzantine Agreement (BA) is a key component in many distributed systems. While Dolev and Reischuk have proven a long time ago that quadratic communication complexity is necessary for worst-case runs, the question of what can be done in practically common runs with fewer failures remained open. In this paper we present the first Byzantine Broadcast algorithm with O(n(f+1)) communication complexity in a model with resilience of n = 2t+1, where 0 ≤ f ≤ t is the actual number of process failures in a run. And for BA with strong unanimity, we present the first optimal-resilience algorithm that has linear communication complexity in the failure-free case and a quadratic cost otherwise.
Cite as

Shir Cohen, Idit Keidar, and Alexander Spiegelman. Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2022.18,
  author =	{Cohen, Shir and Keidar, Idit and Spiegelman, Alexander},
  title =	{{Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{18:1--18:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.18},
  URN =		{urn:nbn:de:0030-drops-176385},
  doi =		{10.4230/LIPIcs.OPODIS.2022.18},
  annote =	{Keywords: Byzantine Agreement, Byzantine Broadcast, Adaptive communication}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.29
On Payment Channels in Asynchronous Money Transfer Systems

Authors: Oded Naor and Idit Keidar

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Money transfer is an abstraction that realizes the core of cryptocurrencies. It has been shown that, contrary to common belief, money transfer in the presence of Byzantine faults can be implemented in asynchronous networks and does not require consensus. Nonetheless, existing implementations of money transfer still require a quadratic message complexity per payment, making attempts to scale hard. In common blockchains, such as Bitcoin and Ethereum, this cost is mitigated by payment channels implemented as a second layer on top of the blockchain allowing to make many off-chain payments between two users who share a channel. Such channels require only on-chain transactions for channel opening and closing, while the intermediate payments are done off-chain with constant message complexity. But payment channels in-use today require synchrony; therefore, they are inadequate for asynchronous money transfer systems. In this paper, we provide a series of possibility and impossibility results for payment channels in asynchronous money transfer systems. We first prove a quadratic lower bound on the message complexity of on-chain transfers. Then, we explore two types of payment channels, unidirectional and bidirectional. We define them as shared memory abstractions and prove that in certain cases they can be implemented as a second layer on top of an asynchronous money transfer system whereas in other cases it is impossible.
Cite as

Oded Naor and Idit Keidar. On Payment Channels in Asynchronous Money Transfer Systems. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{naor_et_al:LIPIcs.DISC.2022.29,
  author =	{Naor, Oded and Keidar, Idit},
  title =	{{On Payment Channels in Asynchronous Money Transfer Systems}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{29:1--29:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.29},
  URN =		{urn:nbn:de:0030-drops-172201},
  doi =		{10.4230/LIPIcs.DISC.2022.29},
  annote =	{Keywords: Blockchains, Asynchrony, Byzantine faults, Payment channels}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.30
Using Nesting to Push the Limits of Transactional Data Structure Libraries

Authors: Gal Assa, Hagar Meir, Guy Golan-Gueta, Idit Keidar, and Alexander Spiegelman

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Transactional data structure libraries (TDSL) combine the ease-of-programming of transactions with the high performance and scalability of custom-tailored concurrent data structures. They can be very efficient thanks to their ability to exploit data structure semantics in order to reduce overhead, aborts, and wasted work compared to general-purpose software transactional memory. However, TDSLs were not previously used for complex use-cases involving long transactions and a variety of data structures. In this paper, we boost the performance and usability of a TDSL, towards allowing it to support complex applications. A key idea is nesting. Nested transactions create checkpoints within a longer transaction, so as to limit the scope of abort, without changing the semantics of the original transaction. We build a Java TDSL with built-in support for nested transactions over a number of data structures. We conduct a case study of a complex network intrusion detection system that invests a significant amount of work to process each packet. Our study shows that our library outperforms publicly available STMs twofold without nesting, and by up to 16x when nesting is used.
Cite as

Gal Assa, Hagar Meir, Guy Golan-Gueta, Idit Keidar, and Alexander Spiegelman. Using Nesting to Push the Limits of Transactional Data Structure Libraries. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{assa_et_al:LIPIcs.OPODIS.2021.30,
  author =	{Assa, Gal and Meir, Hagar and Golan-Gueta, Guy and Keidar, Idit and Spiegelman, Alexander},
  title =	{{Using Nesting to Push the Limits of Transactional Data Structure Libraries}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.30},
  URN =		{urn:nbn:de:0030-drops-158058},
  doi =		{10.4230/LIPIcs.OPODIS.2021.30},
  annote =	{Keywords: Transactional Libraries, Nesting}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.18
Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer

Authors: Shir Cohen and Idit Keidar

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We formalize Byzantine linearizability, a correctness condition that specifies whether a concurrent object with a sequential specification is resilient against Byzantine failures. Using this definition, we systematically study Byzantine-tolerant emulations of various objects from registers. We focus on three useful objects- reliable broadcast, atomic snapshot, and asset transfer. We prove that there exist n-process f-resilient Byzantine linearizable implementations of such objects from registers if and only if f < n/2.
Cite as

Shir Cohen and Idit Keidar. Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.DISC.2021.18,
  author =	{Cohen, Shir and Keidar, Idit},
  title =	{{Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.18},
  URN =		{urn:nbn:de:0030-drops-148203},
  doi =		{10.4230/LIPIcs.DISC.2021.18},
  annote =	{Keywords: Byzantine linearizability, concurrent algorithms, snapshot, asset transfer}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.45
Brief Announcement: Using Nesting to Push the Limits of Transactional Data Structure Libraries

Authors: Gal Assa, Hagar Meir, Guy Golan-Gueta, Idit Keidar, and Alexander Spiegelman

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Transactional data structure libraries (TDSL) combine the ease-of-programming of transactions with the high performance and scalability of custom-tailored concurrent data structures. They can be very efficient thanks to their ability to exploit data structure semantics in order to reduce overhead, aborts, and wasted work compared to general-purpose software transactional memory. However, TDSLs were not previously used for complex use-cases involving long transactions and a variety of data structures. In this paper, we boost the performance and usability of a TDSL, towards allowing it to support complex applications. A key idea is nesting. Nested transactions create checkpoints within a longer transaction, so as to limit the scope of abort, without changing the semantics of the original transaction. We build a Java TDSL with built-in support for nested transactions over a number of data structures. We conduct a case study of a complex network intrusion detection system that invests a significant amount of work to process each packet. Our study shows that our library outperforms publicly available STMs twofold without nesting, and by up to 16x when nesting is used.
Cite as

Gal Assa, Hagar Meir, Guy Golan-Gueta, Idit Keidar, and Alexander Spiegelman. Brief Announcement: Using Nesting to Push the Limits of Transactional Data Structure Libraries. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 45:1-45:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{assa_et_al:LIPIcs.DISC.2021.45,
  author =	{Assa, Gal and Meir, Hagar and Golan-Gueta, Guy and Keidar, Idit and Spiegelman, Alexander},
  title =	{{Brief Announcement: Using Nesting to Push the Limits of Transactional Data Structure Libraries}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{45:1--45:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.45},
  URN =		{urn:nbn:de:0030-drops-148479},
  doi =		{10.4230/LIPIcs.DISC.2021.45},
  annote =	{Keywords: Transactional Libraries}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.OPODIS.2020.2
Byzantine Agreement and SMR with Sub-Quadratic Message Complexity (Invited Talk)

Authors: Idit Keidar

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Byzantine Agreement (BA) has been studied for four decades by now, but until recently, has been considered at a fairly small scale. In recent years, however, we begin to see practical use-cases of BA in large-scale systems, which motivates a push for reduced communication complexity. Dolev and Reischuk’s well-known lower bound stipulates that any deterministic algorithm requires Ω(n²) communication in the worst-case, and until fairly recently, almost all randomized algorithms have had at least quadratic complexity as well. This talk will present two new algorithms breaking this barrier. The first part of the talk will consider a fully asynchronous setting, focusing on randomized BA whose safety and liveness guarantees hold with high probability. It will present the first asynchronous Byzantine Agreement algorithm with sub-quadratic communication complexity. This algorithm exploits VRF-based committee sampling, which it adapts for the asynchronous model. The second part of the talk will consider the eventually synchronous model, where BA and State Machine Replication (SMR) can be solved with deterministic safety and liveness guarantees. In this context, randomization is used in order to reduce the expected communication complexity. The talk will present an algorithm for round synchronization, which is a building block for BA and SMR and constitutes the main performance bottleneck therein. It will present an algorithm that, for the first time, achieves round synchronization with expected linear message complexity and expected constant latency. Existing protocols can use this round synchronization algorithm to solve Byzantine SMR with the same asymptotic performance. The first part of the talk is based on joint work with Shir Cohen and Alexander Spiegelman, and the second part of the talk is based on joint work with Oded Naor.
Cite as

Idit Keidar. Byzantine Agreement and SMR with Sub-Quadratic Message Complexity (Invited Talk). In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{keidar:LIPIcs.OPODIS.2020.2,
  author =	{Keidar, Idit},
  title =	{{Byzantine Agreement and SMR with Sub-Quadratic Message Complexity}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.2},
  URN =		{urn:nbn:de:0030-drops-134874},
  doi =		{10.4230/LIPIcs.OPODIS.2020.2},
  annote =	{Keywords: Distributed Computing, Byzantine Agreement}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.2
Intermediate Value Linearizability: A Quantitative Correctness Criterion

Authors: Arik Rinberg and Idit Keidar

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Big data processing systems often employ batched updates and data sketches to estimate certain properties of large data. For example, a CountMin sketch approximates the frequencies at which elements occur in a data stream, and a batched counter counts events in batches. This paper focuses on correctness criteria for concurrent implementations of such objects. Specifically, we consider quantitative objects, whose return values are from a totally ordered domain, with a particular emphasis on (ε,δ)-bounded objects that estimate a numerical quantity with an error of at most ε with probability at least 1 - δ. The de facto correctness criterion for concurrent objects is linearizability. Intuitively, under linearizability, when a read overlaps an update, it must return the object’s value either before the update or after it. Consider, for example, a single batched increment operation that counts three new events, bumping a batched counter’s value from 7 to 10. In a linearizable implementation of the counter, a read overlapping this update must return either 7 or 10. We observe, however, that in typical use cases, any intermediate value between 7 and 10 would also be acceptable. To capture this additional degree of freedom, we propose Intermediate Value Linearizability (IVL), a new correctness criterion that relaxes linearizability to allow returning intermediate values, for instance 8 in the example above. Roughly speaking, IVL allows reads to return any value that is bounded between two return values that are legal under linearizability. A key feature of IVL is that we can prove that concurrent IVL implementations of (ε,δ)-bounded objects are themselves (ε,δ)-bounded. To illustrate the power of this result, we give a straightforward and efficient concurrent implementation of an (ε, δ)-bounded CountMin sketch, which is IVL (albeit not linearizable). Finally, we show that IVL allows for inherently cheaper implementations than linearizable ones. In particular, we show a lower bound of Ω(n) on the step complexity of the update operation of any wait-free linearizable batched counter from single-writer objects, and propose a wait-free IVL implementation of the same object with an O(1) step complexity for update.
Cite as

Arik Rinberg and Idit Keidar. Intermediate Value Linearizability: A Quantitative Correctness Criterion. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rinberg_et_al:LIPIcs.DISC.2020.2,
  author =	{Rinberg, Arik and Keidar, Idit},
  title =	{{Intermediate Value Linearizability: A Quantitative Correctness Criterion}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.2},
  URN =		{urn:nbn:de:0030-drops-130801},
  doi =		{10.4230/LIPIcs.DISC.2020.2},
  annote =	{Keywords: concurrency, concurrent objects, linearizability}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.25
Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP

Authors: Shir Cohen, Idit Keidar, and Alexander Spiegelman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
King and Saia were the first to break the quadratic word complexity bound for Byzantine Agreement in synchronous systems against an adaptive adversary, and Algorand broke this bound with near-optimal resilience (first in the synchronous model and then with eventual-synchrony). Yet the question of asynchronous sub-quadratic Byzantine Agreement remained open. To the best of our knowledge, we are the first to answer this question in the affirmative. A key component of our solution is a shared coin algorithm based on a VRF. A second essential ingredient is VRF-based committee sampling, which we formalize and utilize in the asynchronous model for the first time. Our algorithms work against a delayed-adaptive adversary, which cannot perform after-the-fact removals but has full control of Byzantine processes and full information about communication in earlier rounds. Using committee sampling and our shared coin, we solve Byzantine Agreement with high probability, with a word complexity of Õ(n) and O(1) expected time, breaking the O(n²) bit barrier for asynchronous Byzantine Agreement.
Cite as

Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.DISC.2020.25,
  author =	{Cohen, Shir and Keidar, Idit and Spiegelman, Alexander},
  title =	{{Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.25},
  URN =		{urn:nbn:de:0030-drops-131034},
  doi =		{10.4230/LIPIcs.DISC.2020.25},
  annote =	{Keywords: shared coin, Byzantine Agreement, VRF, sub-quadratic consensus protocol}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.26
Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR

Authors: Oded Naor and Idit Keidar

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
State Machine Replication (SMR) solutions often divide time into rounds, with a designated leader driving decisions in each round. Progress is guaranteed once all correct processes synchronize to the same round, and the leader of that round is correct. Recently suggested Byzantine SMR solutions such as HotStuff, Tendermint, and LibraBFT achieve progress with a linear message complexity and a constant time complexity once such round synchronization occurs. But round synchronization itself incurs an additional cost. By Dolev and Reischuk’s lower bound, any deterministic solution must have Ω(n²) communication complexity. Yet the question of randomized round synchronization with an expected linear message complexity remained open. We present an algorithm that, for the first time, achieves round synchronization with expected linear message complexity and expected constant latency. Existing protocols can use our round synchronization algorithm to solve Byzantine SMR with the same asymptotic performance.
Cite as

Oded Naor and Idit Keidar. Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{naor_et_al:LIPIcs.DISC.2020.26,
  author =	{Naor, Oded and Keidar, Idit},
  title =	{{Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.26},
  URN =		{urn:nbn:de:0030-drops-131046},
  doi =		{10.4230/LIPIcs.DISC.2020.26},
  annote =	{Keywords: Distributed Systems, State Machine Replication}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.4
FairLedger: A Fair Blockchain Protocol for Financial Institutions

Authors: Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Financial institutions nowadays are looking into technologies for permissioned blockchains. A major effort in this direction is Hyperledger, an open source project hosted by the Linux Foundation and backed by a consortium of over a hundred companies. A key component in permissioned blockchain protocols is a byzantine fault tolerant (BFT) consensus engine that orders transactions. However, currently available BFT solutions in Hyperledger (as well as in the literature at large) are inadequate for financial settings; they are not designed to ensure fairness or to tolerate the selfish behavior that inevitably arises when financial institutions strive to maximize their own profit. We present FairLedger, a permissioned BFT blockchain protocol, which is fair, deigned to deal with rational behavior, and, no less important, easy to understand and implement. Our secret sauce is a new communication abstraction called detectable all-to-all (DA2A), which allows us to detect players (byzantine or rational) that deviate from the protocol and punish them. We implement FairLedger in the Hyperledger open source project using the Iroha framework - one of the biggest projects therein. To evaluate FairLegder’s performance, we also implement it in the PBFT framework and compare the two protocols. Our results show that in failure-free scenarios in wide-area settings, FairLedger achieves better throughput than both Iroha’s implementation and PBFT.
Cite as

Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. FairLedger: A Fair Blockchain Protocol for Financial Institutions. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{levari_et_al:LIPIcs.OPODIS.2019.4,
  author =	{Lev-Ari, Kfir and Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
  title =	{{FairLedger: A Fair Blockchain Protocol for Financial Institutions}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.4},
  URN =		{urn:nbn:de:0030-drops-117904},
  doi =		{10.4230/LIPIcs.OPODIS.2019.4},
  annote =	{Keywords: Blockchain, Fairness, Byzantine fault tolerance, Rational players, Equilibrium}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.11
Integrated Bounds for Disintegrated Storage

Authors: Alon Berger, Idit Keidar, and Alexander Spiegelman

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We point out a somewhat surprising similarity between non-authenticated Byzantine storage, coded storage, and certain emulations of shared registers from smaller ones. A common characteristic in all of these is the inability of reads to safely return a value obtained in a single atomic access to shared storage. We collectively refer to such systems as disintegrated storage, and show integrated space lower bounds for asynchronous regular wait-free emulations in all of them. In a nutshell, if readers are invisible, then the storage cost of such systems is inherently exponential in the size of written values; otherwise, it is at least linear in the number of readers. Our bounds are asymptotically tight to known algorithms, and thus justify their high costs.
Cite as

Alon Berger, Idit Keidar, and Alexander Spiegelman. Integrated Bounds for Disintegrated Storage. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.DISC.2018.11,
  author =	{Berger, Alon and Keidar, Idit and Spiegelman, Alexander},
  title =	{{Integrated Bounds for Disintegrated Storage}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.11},
  URN =		{urn:nbn:de:0030-drops-98009},
  doi =		{10.4230/LIPIcs.DISC.2018.11},
  annote =	{Keywords: storage, coding, lower bounds, space complexity, register emulations}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.40
Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution

Authors: Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Providing clean and efficient foundations and tools for reconfiguration is a crucial enabler for distributed system management today. This work takes a step towards developing such foundations. It considers classic fault-tolerant atomic objects emulated on top of a static set of fault-prone servers, and turns them into dynamic ones. The specification of a dynamic object extends the corresponding static (non-dynamic) one with an API for changing the underlying set of fault-prone servers. Thus, in a dynamic model, an object can start in some configuration and continue in a different one. Its liveness is preserved through the reconfigurations it undergoes, tolerating a versatile set of faults as it shifts from one configuration to another. In this paper we present a general abstraction for asynchronous reconfiguration, and exemplify its usefulness for building two dynamic objects: a read/write register and a max-register. We first define a dynamic model with a clean failure condition that allows an administrator to reconfigure the system and switch off a server once the reconfiguration operation removing it completes. We then define the Reconfiguration abstraction and show how it can be used to build dynamic registers and max-registers. Finally, we give an optimal asynchronous algorithm implementing the Reconfiguration abstraction, which in turn leads to the first asynchronous (consensus-free) dynamic register emulation with optimal complexity. More concretely, faced with n requests for configuration changes, the number of configurations that the dynamic register is implemented over is n; and the complexity of each client operation is O(n).
Cite as

Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{spiegelman_et_al:LIPIcs.DISC.2017.40,
  author =	{Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
  title =	{{Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.40},
  URN =		{urn:nbn:de:0030-drops-79673},
  doi =		{10.4230/LIPIcs.DISC.2017.40},
  annote =	{Keywords: Reconfiguration, Dynamic Objects, Optimal Algorithm}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.53
Brief Announcement: Towards Reduced Instruction Sets for Synchronization

Authors: Rati Gelashvili, Idit Keidar, Alexander Spiegelman, and Roger Wattenhofer

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and Zhu has shown that computability does not require multicore architectures to support "strong" synchronization instructions like compare-and-swap, as opposed to combinations of "weaker" instructions like decrement and multiply. However, this is the status quo, and in turn, most efficient concurrent data-structures heavily rely on compare-and-swap (e.g. for swinging pointers). We show that this need not be the case, by designing and implementing a concurrent linearizable Log data-structure (also known as a History object), supporting two operations: append(item), which appends the item to the log, and get-log(), which returns the appended items so far, in order. Readers are wait-free and writers are lock-free, hence this data-structure can be used in a lock-free universal construction to implement any concurrent object with a given sequential specification. Our implementation uses atomic read, xor, decrement, and fetch-and-increment instructions supported on X86 architectures, and provides similar performance to a compare-and-swap-based solution on today's hardware. This raises a fundamental question about minimal set of synchronization instructions that the architectures have to support.
Cite as

Rati Gelashvili, Idit Keidar, Alexander Spiegelman, and Roger Wattenhofer. Brief Announcement: Towards Reduced Instruction Sets for Synchronization. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 53:1-53:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gelashvili_et_al:LIPIcs.DISC.2017.53,
  author =	{Gelashvili, Rati and Keidar, Idit and Spiegelman, Alexander and Wattenhofer, Roger},
  title =	{{Brief Announcement: Towards Reduced Instruction Sets for Synchronization}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{53:1--53:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.53},
  URN =		{urn:nbn:de:0030-drops-80201},
  doi =		{10.4230/LIPIcs.DISC.2017.53},
  annote =	{Keywords: Consensus hierarchy, universal construction, synchronization instruction.}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.33
Dynamic Atomic Snapshots

Authors: Alexander Spiegelman and Idit Keidar

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Snapshots are useful tools for monitoring big distributed and parallel systems. In this paper, we adapt the well-known atomic snapshot abstraction to dynamic models with an unbounded number of participating processes. Our dynamic snapshot specification extends the API to allow changing the set of processes whose values should be returned from a scan operation. We introduce the ephemeral memory model, which consists of a dynamically changing set of nodes; when a node is removed, its memory can be immediately reclaimed. In this model, we present an algorithm for wait-free dynamic atomic snapshots.
Cite as

Alexander Spiegelman and Idit Keidar. Dynamic Atomic Snapshots. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2016.33,
  author =	{Spiegelman, Alexander and Keidar, Idit},
  title =	{{Dynamic Atomic Snapshots}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.33},
  URN =		{urn:nbn:de:0030-drops-71028},
  doi =		{10.4230/LIPIcs.OPODIS.2016.33},
  annote =	{Keywords: snapshots, shared memory, dynamic, ephemeral memory}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.OPODIS.2015.2
Dynamic Reconfiguration: A Tutorial (Tutorial)

Authors: Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
A key challenge for distributed systems is the problem of reconfiguration. Clearly, any production storage system that provides data reliability and availability for long periods must be able to reconfigure in order to remove failed or old servers and add healthy or new ones. This is far from trivial since we do not want the reconfiguration management to be centralized or cause a system shutdown. In this tutorial we look into existing reconfigurable storage algorithms. We propose a common model and failure condition capturing their guarantees. We define a reconfiguration problem around which dynamic object solutions may be designed. To demonstrate its strength, we use it to implement dynamic atomic storage. We present a generic framework for solving the reconfiguration problem, show how to recast existing algorithms in terms of this framework, and compare among them.
Cite as

Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic Reconfiguration: A Tutorial (Tutorial). In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2015.2,
  author =	{Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
  title =	{{Dynamic Reconfiguration: A Tutorial}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.2},
  URN =		{urn:nbn:de:0030-drops-65938},
  doi =		{10.4230/LIPIcs.OPODIS.2015.2},
  annote =	{Keywords: Dynamic reconfiguration}
}
Document
Keynote
DOI: 10.4230/LIPIcs.OPODIS.2015.4
Space Bounds for Reliable Storage: Fundamental Limits of Coding (Keynote)

Authors: Alexander Spiegelman, Yuval Cassuto, Gregory Chockler, and Idit Keidar

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
We present here a synopsis of a keynote presentation given by Idit Keidar at OPODIS 2015, the International Conference on Principles of Distributed Systems, which took place in Rennes, France, on December 14-17 2015.
Cite as

Alexander Spiegelman, Yuval Cassuto, Gregory Chockler, and Idit Keidar. Space Bounds for Reliable Storage: Fundamental Limits of Coding (Keynote). In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 4:1-4:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2015.4,
  author =	{Spiegelman, Alexander and Cassuto, Yuval and Chockler, Gregory and Keidar, Idit},
  title =	{{Space Bounds for Reliable Storage: Fundamental Limits of Coding}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{4:1--4:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.4},
  URN =		{urn:nbn:de:0030-drops-65957},
  doi =		{10.4230/LIPIcs.OPODIS.2015.4},
  annote =	{Keywords: distributed storage, impossibility}
}
Document
DOI: 10.4230/DagSemProc.06371.4
Denial of Service Protection with Beaver

Authors: Gal Badishi, Idit Keidar, Amir Herzberg, Oleg Romanov, and Avital Yachin

Published in: Dagstuhl Seminar Proceedings, Volume 6371, From Security to Dependability (2007)

Abstract
We present Beaver, a method and architecture to ``build dams'' to protect servers from Denial of Service (DoS) attacks. Beaver allows efficient filtering of DoS traffic using low-cost, high-performance, readily-available packet filtering mechanisms. Beaver improves on previous solutions by not requiring cryptographic processing of messages, allowing the use of efficient routing (avoiding overlays), and establishing keys and state as needed. We present two prototype implementations of Beaver, one as part of IPSec in a Linux kernel, and a second as an NDIS hook driver on a Windows machine. Preliminary measurements illustrate that Beaver withstands severe DoS attacks without hampering the client-server communication. Moreover, Beaver is simple and easy to deploy.
Cite as

Gal Badishi, Idit Keidar, Amir Herzberg, Oleg Romanov, and Avital Yachin. Denial of Service Protection with Beaver. In From Security to Dependability. Dagstuhl Seminar Proceedings, Volume 6371, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{badishi_et_al:DagSemProc.06371.4,
  author =	{Badishi, Gal and Keidar, Idit and Herzberg, Amir and Romanov, Oleg and Yachin, Avital},
  title =	{{Denial of Service Protection with Beaver}},
  booktitle =	{From Security to Dependability},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6371},
  editor =	{Christian Cachin and Felix C. Freiling and Jaap-Henk Hoepman},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06371.4},
  URN =		{urn:nbn:de:0030-drops-8492},
  doi =		{10.4230/DagSemProc.06371.4},
  annote =	{Keywords: Denial of Service}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact